/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/palindrome-pairs
   @Language: C++
   @Datetime: 19-06-17 11:13
   */

class Solution {
	bool isPalindrome(string &s, int begin, int end){
		for(int i=begin, j=end-1; i<j; ++i, --j)
			if(s[i]!=s[j]) return false;
		return true;
	}
public:
	/**
	 * @param words: a list of unique words
	 * @return: all pairs of distinct indices
	 */
	vector<vector<int> > palindromePairs(vector<string> &words) {
		// Write your code here
		vector<vector<int> > vs;
		unordered_map<string,int> pos;
		for(int i=words.size(); i--; pos[words[i]]=i);
		for(int i=0; i<words.size(); ++i){
			for(int j=words[i].length(); j; --j){
				if(isPalindrome(words[i],0,j)){
					string right=words[i].substr(j);
					reverse(right.begin(),right.end());
					if(pos.count(right) && i!=pos[right]) vs.push_back({pos[right],i});
				}
			}
			for(int j=0; j<=words[i].length(); ++j){
				if(isPalindrome(words[i],j,words[i].length())){
					string left=words[i].substr(0,j);
					reverse(left.begin(),left.end());
					if(pos.count(left) && i!=pos[left]) vs.push_back({i,pos[left]});
				}
			}
		}
		return vs;
	}
};
